package codetop.microsoft.T40;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: 18362
 * @Create: 2022-09-07 13:49:02 星期三
 */
class Solution {
    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> ans = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates, target, 0, 0);
        return res;
    }

    private void dfs(int[] candidates, int target, int sum, int cur) {
        if (sum > target || cur > candidates.length)
            return;
        if (sum == target) {
            res.add(new ArrayList<>(ans));
            return;
        }
        for (int i=cur; i<candidates.length; ++i) {
            if (i > cur && candidates[i] == candidates[i-1])
                continue;
            ans.add(candidates[i]);
            dfs(candidates, target, sum + candidates[i], i+1);
            ans.remove(ans.size()-1);
        }
    }
}